/**
 * 
 * https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

*/
/**
 * 解题思路：
 * 1.循环每words长度的子字符串，然后比较里面的内容是否满足words里的
 * O(n*m)
 * 300ms
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    let left=0;
   let wordLen=words[0].length
   let allWordLen=wordLen*words.length;
    let step=1;
    let right=allWordLen;
    let res=[];

     while(right<=s.length){
        const cur=s.substring(left,right);
       
        if(isCombo(cur,words)){
            res.push(left)
        }
        // console.log(cur,left,right,res)
        left+=step;
        right+=step;
    }
    return res;
};

function isCombo(cur,words){
    let wordLen=words[0].length
   let allWordLen=wordLen*words.length;
   let tempWords=[...words]
   // 判断是否包含子串
   for (let start = 0,end=wordLen; end <= allWordLen; start+=wordLen,end+=wordLen) {
    const element = cur.substring(start,end)
    const dupIndex = tempWords.indexOf(element)
        if( dupIndex === -1){
            return false;
        }else{
            tempWords[dupIndex]=''
        }
   }
   return true;
}
// findSubstring("barfoofoobarthefoobarman",["foo","bar","the"]) //ok

// findSubstring("wordgoodgoodgoodbestword",["word","good","best","good"])







// indexof速度太慢了，所以要
var findSubstring2 = function(s, words) {
    let left=0;
   let wordLen=words[0].length
    let right=wordLen;
    let res=[];
    let tempWords=[...words];
    let wordsArrLen=words.length;
     while(right<=s.length){
      
        const cur=s.substring(right-wordLen,right);
    
        const dupIndex = tempWords.indexOf(cur)
        console.log("before",cur,left,right,dupIndex,tempWords,res,)

        

        //检查是否有词组子串
        if( dupIndex === -1){
            // 不匹配则左指针往右走
            left++;
            right=left+wordLen
            tempWords=[...words];
            wordsArrLen=words.length;
        }else{
            //匹配到了右指针往右走
            tempWords[dupIndex]=undefined;
            right+=wordLen;
            wordsArrLen--;
        }

        //如果全匹配则添加结果，并且重置
        if(wordsArrLen===0){
            res.push(left)
            left++;
            right=left+wordLen
            tempWords=[...words];
            wordsArrLen=words.length;
           
        }
        
       console.log("after",cur,left,right,dupIndex,wordsArrLen,res,)
       
       
    }
    //console.log(res)
    return res;
};

// findSubstring2("wordgoodgoodgoodbestword",["word","good","best","good"])
// findSubstring2("barfoofoobarthefoobarman",["foo","bar","the"])
findSubstring2("aaaaaaaaaaaaaa",["aa","aa"])



var findSubstring2 = function(s, words) {
    let left=0;
   let wordLen=words[0].length
    let right=wordLen;
    let res=[];
    let tempWords=[...words];
    let wordsArrLen=words.length;
     while(right<=s.length){
      
        const cur=s.substring(right-wordLen,right);
    
        const dupIndex = tempWords.indexOf(cur)
        console.log("before",cur,left,right,dupIndex,tempWords,res,)

        

        //检查是否有词组子串
        if( dupIndex === -1){
            // 不匹配则左指针往右走
            left++;
            right=left+wordLen
            tempWords=[...words];
            wordsArrLen=words.length;
        }else{
            //匹配到了右指针往右走
            tempWords[dupIndex]=undefined;
            right+=wordLen;
            wordsArrLen--;
        }

        //如果全匹配则添加结果，并且重置
        if(wordsArrLen===0){
            res.push(left)
            left++;
            right=left+wordLen
            tempWords=[...words];
            wordsArrLen=words.length;
           
        }
        
       console.log("after",cur,left,right,dupIndex,wordsArrLen,res,)
       
       
    }
    //console.log(res)
    return res;
};

// findSubstring2("wordgoodgoodgoodbestword",["word","good","best","good"])
// findSubstring2("barfoofoobarthefoobarman",["foo","bar","the"])
findSubstring2("aaaaaaaaaaaaaa",["aa","aa"])